const swap = (arr, i, j) => {
  if (i === j) return;
  // [arr[i], arr[j]] = [arr[j], arr[i]];
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
};

// 1. 冒泡
const bubbleSort = (arr) => {
  if (!Array.isArray(arr)) return;
  const len = arr.length;
  // 外层循环控制轮数，一共需要 len - 1 轮
  for (let i = 0; i < len - 1; i++) {
    // 每一轮都把最大的冒泡到最后
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
};

// 2. 选择
const selectionSort = (arr) => {
  if (!Array.isArray(arr)) return;
  const len = arr.length;
  let minIndex = 0;
  // 每个位置依次填入最小值，每一轮都选出一个最小值，填入对应位置，一共需要 len - 1 轮
  for (let i = 0; i < len - 1; i++) {
    minIndex = i;
    // 每一轮都从 i + 1 开始找最小值
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 找到最小值后，和 i 位置交换，之后下一轮重置 minIndex
    swap(arr, i, minIndex);
  }
};

// 3. 插入
const insertionSort = (arr) => {
  if (!Array.isArray(arr)) return;
  const len = arr.length;
  // 从第二个位置开始，提出当前索引的值，依次向前比较，
  // 如果是更大的值，就向后移位，腾出插入空间，直到找到合适的位置插入
  for (let i = 1; i < len; i++) {
    const target = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > target) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = target;
  }
};

// 归并
const merge = (left, right) => {
  const res = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      res.push(left.shift());
    } else {
      res.push(right.shift());
    }
  }
  return [...res, ...left, ...right];
};
// 4. 归并
const mergeSort = (arr) => {
  // if (!Array.isArray(arr)) throw new Error('请输入数组'); // 递归中不好重复判断
  const len = arr.length;
  // 递归地进行左右拆分，直到拆分到单个元素
  if (len <= 1) return arr;
  const mid = Math.floor(len / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
};

// 5. 快排
const quickSort = (arr) => {
  // 阮氏快排 空间复杂度需要优化 非in-place（原地）排序，每轮递归都需要额外的空间
  // if (!Array.isArray(arr)) throw new Error('请输入数组'); // 递归中不好重复判断
  const len = arr.length;
  if (len <= 1) return arr;
  // 每轮递归都选择一个基准值，将数组分为左右两部分，左边的值都小于等于基准值，右边的值都大于等于基准值
  const pivotIndex = Math.floor(len / 2);
  const pivot = arr[pivotIndex];
  const left = [];
  const right = [];
  for (let i = 0; i < len; i++) {
    if (i === pivotIndex) continue;
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
};

// 优化：双指针法，空间复杂度 O(1)  in-place排序
const quickSort2 = (arr, left = 0, right = arr.length - 1) => {
  if (!Array.isArray(arr)) throw new Error('请输入数组');
  if (typeof left !== 'number' || typeof right !== 'number') throw new Error('请输入正确的左右边界');
  // 每轮递归都选择一个基准值，将数组分为左右两部分，左边的值都小于等于基准值，右边的值都大于等于基准值
  if (left >= right) return;
  // 先假设最左边为基准值
  const pivot = arr[left];
  let i = left; // left + 1; // 左指针 （考虑边界情况，这里不能取left+1，否则 left+1 的位置就没有参与比较了）
  let j = right; // 右指针
  while (i < j) {
    // 从右往左 找第一个小于基准值的元素 即需要往左边移的元素
    /* （考虑边界情况，最好先从右往左找，否则最后一次i++ 后，i j相遇时，都指向一个
       应该在右边的值了，导致基准值归位swap时需要 跟 i-1 交换，而不是 i ） */
    while (i < j && arr[j] >= pivot) {
      j--;
    }
    // 从左往右 找第一个大于基准值的元素 即需要往右边移的元素
    while (i < j && arr[i] <= pivot) {
      i++;
    }
    // j 一个需要往左边移，i 一个需要往右边移， 交换
    if (i < j) {
      swap(arr, i, j);
    }
    // 继续循环 直到 i j 相遇
  }
  // 基准值归位  i j 相遇的位置就是基准值应该放的位置
  swap(arr, left, i);
  // 递归处理左右两边
  quickSort2(arr, left, i - 1);
  quickSort2(arr, i + 1, right);
};

// test
const fn = (sortFunc) => {
  const arr = [3, 44, 17, 38, 5, 47, 15, 36, 71, 26, 27, 2, 46, 66, 4, 77, 19, 50, 48, 53, 81];
  console.time('sort');
  const res = sortFunc(arr);
  console.timeEnd('sort');
  console.log(res || arr);
};
fn(bubbleSort);
fn(selectionSort);
fn(insertionSort);
fn(mergeSort);
fn(quickSort);
fn(quickSort2);
